Elementary number theory
Elementary number theory
AaronDefinition I 整除
Let a and b be integers, b ≠ a. If there exists an integer c such that a = bc, then we say that a is divisible by b or \(a \mid b\).
Lemma 1
Let a and b be integers. If \(a \mid b\), then \((-a) \mid b\), \((-a) \mid (-b)\), \(a \mid (-b)\), \(\left\lvert a\right\rvert \mid \left\lvert b\right\rvert\).
Proof:
\[ \because a \mid b \] \[ \therefore \exists c \in \mathbb{Z}, \text{ such that } b = ac. \] \[ \therefore b = (-a)(-c), -b = (-a)c \therefore -b = a(-c), \left\lvert b\right\rvert = \left\lvert a\right\rvert \left\lvert c\right\rvert. \]
Lemma 2
Let a, b, c be integers. If \(a \mid b\), \(b \mid c\), then \(a \mid c\).
Lemma 3
Let a, b be integers. If \(\left\lvert a\right\rvert < \left\lvert b\right\rvert\), and \(\left\lvert b\right\rvert \mid \left\lvert a\right\rvert\), then a = 0.
Proof:
Suppose a ≠ 0, \[ \because \left\lvert b\right\rvert \mid \left\lvert a\right\rvert \] \[ \therefore \exists c \in \mathbb{Z}^{+}, \text{ such that } \left\lvert a\right\rvert = c\left\lvert b\right\rvert \] \[ \therefore \left\lvert b\right\rvert > \left\lvert a\right\rvert = c\left\lvert b\right\rvert \geq \left\lvert b\right\rvert = \left\lvert b\right\rvert \] \[ \therefore \left\lvert b\right\rvert > \left\lvert b\right\rvert \] Contradiction! \[ \therefore a = 0. \]
Lemma 4
Let a and b be positive integers. Then there exists a unique integer pair (q,r) such that:
\[ a = bq + r \text{ for } r \in (0, b) \]
Proof: Existence and Uniqueness
Case I: If \(a \mid b\):
Then \(\exists q \in \mathbb{Z}^{+}\) such that a = bq + 0.
Case II: If \(a \nmid b\):
Existence:
\[ \because a \nmid b \] \[ \therefore a \text{ is located between } kb \text{ and } (k+1)b \text{ for some } k \in \mathbb{Z}^{+} \] \[ \therefore kb < a < (k+1)b \] \[ 0 < a - kb < b \] Let r = a - kb: \[ a = kb + r \text{ for } r \in [0, b] \]
Uniqueness:
Suppose there exist \((q_{1}, r_{1})\) and \((q_{2}, r_{2})\) such that:
\[ a = bq_{1} + r_{1} \quad (1) \] \[ a = bq_{2} + r_{2} \quad (2) \] \[ (1) - (2) \Rightarrow 0 = b(q_{1} - q_{2}) + (r_{1} - r_{2}) \quad (3) \] \[ -(r_{1} - r_{2}) = b(q_{1} - q_{2}) \] \[ \left\lvert r_{1} - r_{2} \right\rvert = b\left\lvert q_{1} - q_{2} \right\rvert \] \[ \Rightarrow b \mid \left\lvert r_{1} - r_{2} \right\rvert \] \[ \because \left\lvert r_{1} - r_{2} \right\rvert < b \] \[ \therefore r_{1} - r_{2} = 0 \text{ (By Lemma 3)} \] \[ \therefore r_{1} = r_{2} \text{ (substitute into (3))} \] \[ \Rightarrow b(q_{1} - q_{2}) = 0 \] \[ \therefore q_{1} - q_{2} = 0 \quad q_{1} = q_{2} \] Contradiction!
Definition II 素数
Integers that are ≥ 2 and can only be divisible by 1 and themselves are called Prime numbers.
Definition III 合数
Integers that are ≥ 2 and can be divisible by other integers are called Composite numbers.
Definition IV 素因数
Let a be a prime integer. Let b be a factor of a. If b is prime, then we call b a prime factor of a.
Lemma 5
Let a be a positive integer, a > 1. Then the smallest positive factor that is greater than 1 of a must be prime.
Proof:
Let b be the smallest factor of a, b > 1.
a must be a composite.
Suppose b is not a prime.
Then b = cd, where \(c, d \in [1, b]\).
\[ \therefore c \mid d, \quad b \mid a \] \[ \therefore c \mid a \quad c \text{ is a factor of } a. \] Contradiction!
Lemma 6
Let a be a positive integer. If a is not divisible by all primes that are \(≤ \sqrt{a}\), then a is a prime.
Proof:
Suppose a is not a prime.
\[ \exists b, c \in \mathbb{Z}^{+}, \text{ such that } a = bc \text{ for } b, c \in [0, a] \] \[ \therefore b > \sqrt{a}, \quad c > \sqrt{a} \] \[ \therefore a = bc > \sqrt{a} \times c > \sqrt{a} \sqrt{a} = a \] \[ \therefore a < a \] Contradiction!
Lemma 7
There are infinitely many primes.
Derived Q: There are infinitely many primes of the form 4n - 1.
Proof:
Suppose that there are finitely many primes of the form 4n - 1 which are \(P_{1}, P_{2}, ..., P_{n}\).
\[ (4a + 1)(4b + 1) = 4(4ab + a + b) + 1 \]
Let P = 4P_{1}P_{2}P_{3}...P_{m} - 1.
P_{i} P for i = 1, 2, ..., m.
\[ \therefore P \text{ must have a prime number of the form } 4n - 1, \text{ but we cannot get a number in the form } 4n - 1 \text{ only from primes of the form } 4n - 1. \] Contradiction!
Definition V 最大公约数
Let \(a_{1}, a_{2}, ..., a_{n}\) be integers.
Let d be a positive integer.
If \(d \mid a_{1}, d \mid a_{2}, ..., d \mid a_{n}\), then we call \(d\) a common factor of \(a_{1}, a_{2}, ..., a_{n}\).
Then d is called the Greatest Common Divisor of \(a_{1}, a_{2}, ..., a_{n}\).
Written as \((a_{1}, a_{2}, ..., a_{n})\) or \(gcd(a_{1}, a_{2}, ..., a_{n})\).
Lemma 8
Let \(a, b \in \mathbb{Z}^{+}\).
\(b ≠ 0, b \nmid a.\)
Let a = bq + r, when \(q, r \in \mathbb{Z}_{+}.\)
Then \(\gcd(a, b) = \gcd(b, r)\).
Proof:
Let \(gcd(a, b) = d_{1}, gcd(b, r) = d_{2}.\)
Then \(d_{1} \mid a, d_{1} \mid b\).
\[ \because d_{1} \mid r \] \[ \because d_{1} \text{ is a common factor of } b, r \] \[ \therefore d_{1} \leq d_{2} \] \[ \because d_{2} \mid b, \quad d_{2} \mid r \] \[ \because d_{2} \mid a \] \[ \because d_{2} \text{ is a common factor of } a, b \] \[ \therefore d_{2} \leq d_{1} \] \[ \therefore d_{1} = d_{2} \] \(i.e:\) \((a, d) = (b, r)\)
Definition VI 互素
Let \(a_{1}, a_{2}, ..., a_{n}\) be positive integers. If \((a_{1}, a_{2}, ..., a_{n}) = 1\), then we say that \(a_{1}, a_{2}, ..., a_{n}\) are coprime to each other.
\(e.g:\) (6, 10, 15) = 1.
\((6, 10) = 2, (10, 15) = 5, (6, 15) = 3\).
Definition VII
Let \(a_{1}, a_{2}, ..., a_{n}\) be positive numbers. Let \(m\) be a positive number.
If \(a_{1} \mid m, a_{2} \mid m, ..., a_{n} \mid m\), then we call m the common multiple of \(a_{1}, a_{2}, ..., a_{n}\).
Then the smallest positive common multiple of \(a_{1}, a_{2}, ..., a_{n}\) is called the Least Common Multiple of \(a_{1}, a_{2}, ..., a_{n}\).
Written as \([a_{1}, a_{2}, ..., a_{n}]\) or \(lcm(a_{1}, a_{2}, ..., a_{n})\).
Lemma 9
Let \(a, b \in \mathbb{Z}^{+}\).
Let \(m = [a, b]\).
Let \(m'\) be a common multiple of \(a, b\).
Then \(m' \mid m\).
Proof:
Suppose \(m \nmid m'\).
Then \(m' = qr, r \in (0, m)\).
\[ \because m' \text{ is a common multiple}, \quad m = [a, b] \] \[ \therefore a \mid m, \quad b \mid m, \quad a \mid m', \quad b \mid m' \] \[ \therefore a \mid r, \quad b \mid r \] \[ \therefore r \text{ is a common multiple of } a, b \]
Lemma 10
Let \(a, b\) be positive integers.
Let \(d = (a, b), m = [a, b].\)
Then \(ab = dm\).
Proof:
\[ \because ab \text{ is } a\text{'s common multiple}. \] \[ \therefore m \mid ab \text{ (by Lemma 9)}. \] \[ \therefore \exists q \in \mathbb{Z}^{+} \text{ such that } ab = mq. \] \[ \Leftrightarrow \frac{m}{a} = \frac{b}{q}, \quad \frac{m}{b} = \frac{a}{q}. \] \[ \therefore \frac{m}{a}, \frac{m}{b} \text{ are integers}. \] \[ \therefore m \mid a, \quad m \mid b. \] \[ \therefore m = [a, b]. \] \[ \therefore q \mid a, \quad q \mid b, \quad q \text{ is a common factor}. \] \[ \therefore q \leq d. \] \[ \because d \mid bm. \] \[ \therefore \exists m \in \mathbb{Z}^{+} \text{ such that } ab = dm'. \] \[ \therefore b \mid m', \quad a \mid m'. \] \[ \therefore m' \text{ is a common multiple}. \] \[ \therefore m' \geq m. \] \[ d = \frac{ab}{m} \leq \frac{ab}{m} = q. \] \[ \therefore d \leq q. \] Sum up d = q.
\(i.e.\) ab = dm.
Lemma 11
Let a be a positive number which is ≥ 1.
Then a can be written as a product of primes.
Proof: Method 1 无穷递降法
If a is a prime, then the statement is true.
If a is not a prime, then:
Let \(p_{1}\) be the smallest common factor of \(a\).
Then \(a = p_{1}a_{1}\) for some a$ ^{+}$, where \(a > a_{1} > 1\).
We can continue the process to have \(p_{1}, p_{2}, ..., p_{n}\), which are all primes, such that:
\(a = p_{1}p_{2}...p_{n} \times a_{n}\).
Until \(a_{n}\) is a prime.
\[ \therefore \text{ We can write } a \text{ as a product of primes}. \]
Proof: Method 2 Strong Induction
Step 1: For a = 2, which is a prime.
The statement is true for a = 2.
Step 2: Suppose for \(a \in [2, k)\), a can be written as a product of primes.
Step 3: Consider the case for \(a = k + 1\).
If \(k + 1\) is a prime, then the statement is true.
If \(k + 1\) is not a prime, then \(k + 1\) has a prime factor P (by Lemma 5).
Then \(k + 1 = pq\), where \(q \in (2, k + 1]\),
\(i.e., q \in (2, k)\).
By Step 2, we know that q can be written as a product of primes, say \(q = q_{1}q_{2}...q_{n}\), which are all primes.
\[ \therefore k + 1 = pq = p \times q_{1}q_{2}...q_{n}, \text{ which is a product of primes}. \]
Lemma 12
Let a, p be prime integers.
Then p a if and only if () \((a, p) = 1\).
Proof: \((\Rightarrow)\) only if.
\[ \because (p, a) \mid p \] \[ \therefore (p, a) = 1 \text{ or } p. \] \[ \because \text{ If } (a, p) = p, \text{ then } p \mid a. \text{ Contradiction!} \] \[ \therefore (p, a) = 1 \]
Proof: \((\Leftarrow)\) if.
Suppose \(p \mid a\).
\[ \therefore p \text{ is a common factor of } a \text{ and } p. \] \[ \therefore (a, p) = 1 < p, \text{ Contradiction!} \] \[ \therefore p \nmid a. \]
Lemma 13
Let a, b, c be positive integers such that \((a, b) = 1, a \mid bc\).
Then \(a \mid c\).
Proof:
\[ \because (a, b) = 1. \] \[ \therefore [a, b] = ab \text{ (By Lemma 10)}. \] \[ \because b \mid bc, \quad a \mid bc. \] \[ \therefore bc \text{ is a common factor of } a \text{ and } b. \] \[ \therefore [a, b] \mid bc \text{ (By Lemma 9)}. \] \[ \therefore ab \mid bc. \] \[ \therefore a \mid c. \]
Lemma 14
Let \(4n ≥ 2\). Let \(a_{1}, a_{2}, ..., a_{n}\) be positive integers.
If \(a \mid a_{1}, a_{2}, ..., a_{n}\) and \((a, a_{1}) = (a, a_{2}) = ... = (a, a_{n}) = 1\).
Then \(a \mid a_{n}\).
Proof:
\[ \because (a, a_{1}) = 1, \quad a \mid a_{1}a_{2}...a_{n}. \] \[ \therefore a \mid a_{2}...a_{n} \text{ (By Lemma 13)} \] \[ \because (a, a_{2}) = 1. \] \[ \therefore a \mid a_{2}a_{3}...a_{n} \] \[ \vdots \] \[ a \mid a_{n-1}a_{n} \] \[ \because (a, a_{n-1}) = 1. \] \[ \therefore a \mid a_{n}. \]
Lemma 15
Let \(a, b, c\) be positive integers.
If \((a, b) = 1\), \(c \mid a\) then \((b, c) = 1\).
Proof:
Let \((b, c) = d\).
\[ \therefore d \mid c, \quad c \mid a. \] \[ \therefore d \mid a. \] \[ \because d \mid b, \quad d \mid a. \] \[ \therefore d \text{ is a common factor of } a \text{ and } b. \] \[ \therefore d = 1. \quad i.e: (b, c) = 1. \]
Lemma 16
Let \(a, b\) be positive integers, such that \((a, b) = 1\).
Then \((a, bc) = (a, c)\).
Proof:
Let \((a, c) = d_{1}\), \((a, bc) = d_{2}\).
\[ \because d_{1} \mid c. \] \[ \therefore d_{1} \mid bc. \] \[ \because d_{1} \mid bc, \quad d_{1} \mid a. \] \[ \therefore d_{1} \leq d_{2}. \] \[ \therefore d_{2} \mid bc, \quad d_{2} \mid a, \quad (a, b) = 1. \]
Let \((d_{2}, b) = m\), m d_{2}, m b.
\[ \because d_{2}, b. \]
\[ \therefore m \mid a. \]
\[ \therefore m \text{ is a common factor}. \]
\[ \therefore m \geq 1. \]
\[ \therefore m = 1. \]
\[ (d_{2}, b) = 1, d_{2} \mid bc. \]
\[ \therefore d_{2} \mid c. \] \[ \therefore d_{2} \mid a, \quad d_{2} \mid c. \] \[ \because d_{2} \text{ is a common factor}. \] \[ \therefore d \leq d_{1}. \] \[ \therefore d_{1} = d_{2}. \]
Lemma 17
Let \(n ≥ 2\) be an integer.
Let \(a, b_{1}, b_{2}, ..., b_{n}\) be positive integers.
\((a, b_{1}) = 1, (a, b_{2}) = ... = (a, b_{n}) = 1\).
Then \((a, b_{1}, b_{2}, ..., b_{n}) = 1\).
Proof:
\[ \because (a, b_{1}) = 1. \] \[ \therefore (a_{1}, b_{1}, b_{2}, ..., b_{n}) = (a_{1}, b_{2}, b_{3}, ..., b_{n}). \] \[ \therefore (a, b_{2}) = 1. \] \[ \therefore (a_{1}, b_{1}, b_{2}, ..., b_{n}) = (a_{1}, b_{2}, b_{3}, ..., b_{n}) = (a_{1}, b_{n}) = (a_{1}, b_{n}) = ... = 1. \]
Lemma 18
Let \(n ≥ 2\) be a positive integer.
Let \(p\) be a prime.
Let \(a_{1}, a_{2}, ..., a_{n}\) be positive integers.
If \(p \mid a_{1}a_{2}...a_{n}\) then \(p \mid a_{r}\), for some \(r \in \{1, 2, ..., n\}\).
Proof:
Suppose \(\forall r \in \{1, 2, ..., n\}, p \nmid a_{r}\).
\[ \therefore (p, a_{r}) = 1 \text{ (By Lemma 12)}. \] \[ \therefore (p, a_{1}a_{2}...a_{n}) = (p, a_{2}a_{3}...a_{n}) = ... = (p \mid a_{n}) = 1 \] \[ \therefore p \nmid a_{1}a_{2}...a_{n}. \]
Lemma 19
Let \(n ≥ 2\) be an integer.
Let \(p, p_{1}, p_{2}, ..., p_{n}\) be primes.
If \(p \mid p_{1}p_{2}...p_{n}\) then \(p = p_{n}\) for some \(r \in \{1, 2, ..., n\}\).
Proof:
By Lemma 18, p p_{r} for some r {1, 2, ..., n}.
\[ \therefore p_{r} \text{ has only factors which are } 1, p_{r}. \] \[ \because p \neq 1, \therefore p = p_{r}. \]
Theorem: Fundamental Theorem of Arithmetic
There is a unique way to factorize a positive integer greater than or equal to 2 into a product of primes, given that the order of the primes does not matter.
Proof:
Existence has been proved in Lemma 11.
Uniqueness: Suppose there exist two different prime factorizations of \(a \in \mathbb{Z}^{+}\), \(a \geq 2\).
Let \(a = p_{1}p_{2} \cdots p_{k} = q_{1}q_{2} \cdots q_{m}\), where \(p_{i}\) and \(q_{j}\) are primes.
\[ \therefore p_{1} \mid q_{1}q_{2}...q_{m} \]
\[ p_{1} = q_{r}, \text{ for some } r \in \{1, 2, ..., n\} \text{ (By Lemma 19)}. \]
Without loss of generality (WLOG), let p_{1} = q_{1}.
\[ \therefore p_{2}p_{3} \cdots p_{n} = q_{2}q_{3}q_{m}. \]
We can repeat the process until \[ p_{2} = q_{2}, p_{3} = q_{3}, ..., p_{n} = q_{m}, m = n \].
\[ \therefore a = p_{1}p_{2} \cdots p_{k} = q_{1}q_{2} \cdots q_{m} \]
These are the same prime factorization.
\(Contradiction!\)
